1. Field of the Invention
The invention relates to apparatus and accompanying methods for optimally using available computer resources, illustratively processing time, and is ideally, though not exclusively, suited for selecting task(s) instances to be precomputed during idle, as well as during other periods of processing activity.
2. Description of the Prior Art
Generally speaking, a single computer processor, while executing a given software program and under control of an associated operating system, executes a series of atomistic processes--which collectively implement the program. However, in any single sequential Von Neumann type processor, only one such process executes at any one time. A significant response time imbalance often exists between a rate at which the processor itself executes instructions for a given process and the substantially slower response time of a resource, e.g. a hard disk drive or other mass storage facility, utilized by that processor. Hence, when the process requires use of such a resource, the operating system issues a request for the resource and then ceases executing the process, i.e. the process is suspended and simply waits, until the resource has properly responded to the request. This wait time can become significant if the resource is busy, i.e. unavailable, at the time the request is issued. While the process itself could not advance its execution pending the availability of the resource, the computer processor itself is often not so constrained.
The art, recognizing this dichotomy and given the widely divergent response times between a processor used in a computer system and other associated resources therein, teaches several techniques aimed at increasing computer utilization, and thus increasing throughput, by exploiting concurrency. All these techniques are characterized, in some form or another, by utilizing time, whether it be processing time and/or resource time, that would otherwise be spent simply waiting for something, such as a particular event, to occur and thus be wasted.
One such concurrency technique involves so-called "multi-tasking" through which a portion of a process, the portion commonly referred to as a "thread", is separately executable. Each thread has its own distinct program counter and represents a separate movement of a processor through a program instruction space. Rather than requiring a computer processor to execute a single unitary process or program from start to finish with intermediate wait (idle) intervals and potentially substantially wasted processing time, a single thread is executed at any one time but not necessarily to completion. A thread will continuously execute until either its execution is interrupted or that thread must wait for an associated resource which it then requires to become available. Once execution so ceases for a given thread, the computer, through context switching, begins executing another thread then queued for execution. Multi-threaded operation provides the illusion, given the relatively high processing speeds relative to that of other resources in the computer, of simultaneous execution of multiple threads and more generally of multiple programs. While the incorporation of context switching increases the amount of processing overhead consumed by the operating system, as a function of total available processing time, this increase is rather minor compared to the processing cycles that would otherwise be wasted during single-task processing and are consequently made available for execution of waiting threads. Consequently, multi-tasking provides significantly enhanced throughput over single task operation. As an example of a multi-tasking operating system is the Windows NT operating system currently available from Microsoft Corporation of Redmond, Wash., which is the present assignee hereof (and which also owns the registered trademark "Windows NT").
Further throughput enhancements arise through use of so-called "multi-processing". Rather than utilizing a single computer processor, a "multi-processing" based operating system executes on a computer that employs two or more separate processors which together operate concurrently. Illustratively, the Windows NT operating system not only provides multi-tasking but also accommodates so-called "symmetric multi-processing"; through the latter, any available one of a group of processors in a common computer can execute both operating system code and user (application) code. Additional throughput arises where a multi-processor operating system is also multi-tasking, i.e., as in Windows NT operating system, where each one of a group of processors can operate on a multi-tasked basis by effectively dividing its time among all waiting threads.
Additional concurrency-based throughput enhancements can arise through operating systems that use so-called "multi-threading". Oftentimes, executing two separate processes is not particularly efficient. Such inefficiencies arise where one process, i.e. a "parent" process, must create ("fork") another, i.e. "child", process and copy the contents of the address space of the parent process into that of the child process. This copying consumes a significant amount of time where relatively large address spaces are used. Moreover, the two processes must establish a way to share data therebetween, which, in certain operating systems, is rather difficult to accomplish. To avoid these inefficiencies, a multi-threaded operating system, a capability also inherent in the Windows NT operating system, permits each process to create its own threads, as a need arises to do so. For example, such additional threads are often used for asynchronous operations, i.e. operations (such as input/output, e.g. monitoring user manipulation of a mouse) that can occur at any time without regard to a main flow of the program. By using one thread to run a main program and creating another to monitor a device, the operating system can schedule both operations separately on a given processor to effectuate multi-tasking. When executing on a multi-processing computer, two threads can execute simultaneously, i.e. concurrently, and on different processors without a need for and the concomitant overhead associated with creating a second process and initializing its address space. Concurrency arises where a program creates two or more threads to execute different portions of a common program within the same process but on different processors. For additional detail on threads, multi-tasking, multi-processing and multi-threaded operation, the reader is referred to pages 83-97 of Chapter Four "Processes and Threads" of H. Custer, Inside Windows NT (.COPYRGT. 1993, Microsoft Press).
While these concurrency-based throughput enhancing techniques have substantially increased computer throughput, additional room for improvement exists.
In that regard, even with an operating system, such as the Windows NT operating system, that utilizes multi-threading and multi-tasking, and which can accommodate multi-processing--to the extent it is used in any given computer system, a processor can still spend and waste time idling. This result can simply occur in those instances where, e.g., one thread is currently active but it is waiting for a resource to become available and no other threads are then queued.
In particular, where tasks that form any large processing job are well-organized, well-defined and hence can be tightly scheduled with respect to each other, such as in batch execution of large jobs on mainframe or similar computers, idling and resource wastage tend to be less pronounced. However, in personal computers, given, from the standpoint of the operating system, the wide diversity of tasks, their seemingly random nature of being executed (e.g. a user executing at any time a save or a spell check operation, or a web page access) as well as relatively long periods between the times a user manually executes separate successive tasks, idling and resource wastage can still be rather acute.
Moreover, not every computer, whether it is a personal computer or not, employs any of these concurrency-based throughput enhancing techniques.
Therefore, a need still exists in the art for apparatus and accompanying methods for optimizing the use of available processing time. Preferably, such an optimization should find ready application to a wide range of, if not substantially all, computers, apart from whether any such computer employs any concurrency enhancing technique, such as multi-tasking, multi-processing or multi-threading.
Furthermore and generally speaking, resource wastage, in a computer, is not confined to occurring just during idle time.
Specifically, computational activity, particularly with personal computers, is often marked by bursts of relatively high processing activity interspersed with intervals, usually somewhat long, of relatively low activity. During the latter intervals, low priority tasks, such as background or overhead processing of one form or another, occur. It is during these low activity intervals that some degree of available processing capacity either exists and is not being used, or is being allocated to relatively unimportant (i.e. low priority) tasks. In either case, some or all of this capacity is being wasted. In an interactive personal computer processing environment, high processing activity occurs during, e.g., downloading of an Internet page or other user-initiated operation, such as spell-checking in a word processing program or updating calculations in spreadsheet program. In contrast, low processing activity is typified by waiting for user input, such as for a user to appropriately manipulate a mouse and select, through clicking, a menu-based command for subsequent execution. Inasmuch as background tasks that execute during low processing intervals tend to be of lesser current importance (utility) and hence can usually be deferred, processing efficiency and hence system throughput would rise if, in some fashion, other tasks, of greater importance, could be determined and executed during these intervals.
In fact, further throughput enhancements could occur if computer resources, such as, e.g., processing time, could be allocated, even for use during periods of high activity, to those tasks in order of their current utility to a user rather than in just their order of pendency or priority.
In that regard and at first blush, one skilled in the art would think that those tasks having greater user and/or operational importance could be executed ahead of other pending tasks that either have lesser importance, but which were previously queued for execution, or are even currently executing. Most conventional personal computer operating systems permit a user to assign a priority to a certain task(s). For various application-based tasks, such as printing a document, or various utilities, their priority can be defined through the associated application or utility by, e.g., manual selection of a value in a range delimited by a software implemented slider, or depression of a button associated with a broad class of priorities, e.g. "high", "medium" or "low" priority. As against two pending tasks awaiting execution, the task with a higher priority would typically be dispatched for execution by the operating system ahead of such a task that has a lower priority. For critical system tasks, the operating system itself can assign different priorities among those tasks depending upon the relative importance the operating system ascribes to each of these tasks. The operating system can also permit the user to select a relative importance and hence a priority to those tasks collectively executing in foreground as against those collectively executing in background. Where the operating system is indifferent to task priority, user-specified priorities, to the extent they are used, may be employed to select one task over another for immediate execution. As one can appreciate, a task priority is often fixed and does not change unless, in the case of user-specified priority, the user manually changes it. Consequently, once a conventional operating system assigns a priority to a task, whether based on user selection or otherwise, that task, if invoked, will be queued for execution and will execute, if processing resources are available, ahead of all other pending tasks that have the same or lower priority. Once the task begins executing, its execution continues to completion, unless interrupted pending resource availability with the task resuming once the resource becomes available.
However, the utility of one task to a user vis-a-vis that of other tasks often changes during a given processing session. Task utility is influenced by current and future needs of the user with respect to his(her) application, historical user activity regarding that application, as well as by changes in the processing environment of the computer then being used. In that regard, a task that previously was of low importance to the user could in a given situation become extremely important to that user, thus deserving of an immediate change in priority with concomitantly immediate or very near-term execution relative to other pending and/or executing tasks. Other tasks, typically viewed as being important to that user, could, based on recent user activity, actually diminish in importance to that user and hence be relegated to a low priority with deferred execution. As of yet, given the difficulties associated with classifying tasks based on their current utility, no operating system appears to dynamically assess current task utility, based on these and similar user and system dependent factors, and schedule task execution accordingly.
Given this apparent omission in the art, operating systems frequently execute tasks, by virtue of their fixed priority assignments, that actually have less current utility to a user ahead of those that have greater current utility. This frustrates the user and further exacerbates resource wastage and, from the standpoint of the user, decreases system throughput.
Therefore, apart from a specific need to effectively utilize computer resources, such as available processing time, during idle-time intervals, a broad-based need continues to exist in the art to effectively and efficiently utilize available computer resources in properly selecting and executing tasks for current execution at any time. The solution to this need should assess dynamic changes in the current utility of a task to its user and select tasks for current execution accordingly.